In many data processing applications using computer systems and integrated circuits, arrays of numbers representing data values are stored and manipulated, for example, in the memory of the computer system. For an array of N data values, extremum values (i.e. maxima or minima of the data values), if they exist, are characteristic parameters of the array. Data processing applications utilize such maxima and minima, as well as their respective locations in the array, indicated by an index or pointer to the data values corresponding to the maxima and/or minima.
Heretofore, the determination of maxima and minima in data processing applications, such as in Viterbi processing in equalization and speech processing, has been compute intensive.
One form of digital signal processor (DSP) architecture that exhibits significant benefits in processing speed is known as a Multiply-Accumulate or MAC processor. The MAC processor implements an architecture that takes advantage of the fact that the most common data processing operations involve multiplying two values, then adding the resulting value to another and accumulating the result. These basic operations are efficiently carried out utilizing specially configured, high-speed multipliers and accumulators, hence the "Multiply-Accumulate" nomenclature.
Another method for increasing processing speed is to perform different processes concurrently. Towards this end, DSP architectures with plural MAC structures have been developed. For example, a dual MAC processor is capable of performing two independent MAC operations concurrently.
The DSP16000 dual-MAC processor, available from Lucent Technologies, includes a data arithmetic unit (DAU), which constitutes the primary computational unit. The inputs to the multipliers of the DAU are applied through a pair of double length registers designated as the x and y registers, while the output of each multiplier is applied to a respective product register. Concurrent accumulations are achieved by providing both two-input arithmetic logic unit (ALU) and a three-input adder, either of which may accumulate the data in either product register. When mathematical functions are performed by the ALU or adder, the result is stored in an accumulator register, a number of which are present in the DAU.
Implementations of extrema determination typically use brute force number crunching procedures to accurately determine an extremum and its location in an array of data values. For example, the following pseudo code, which may be implemented in the DSP16000 assembly language, or alternatively in the Pascal or C++ computer languages, may be used to determine a minimum value in an array, ARRAY, of data values:
______________________________________ MIN.sub.-- VALUE = MIN.sub.-- INITIALIZED; MIN.sub.-- INDEX = 0; FOR I = 1 TO N { IF ARRAY[I] &lt; MIN.sub.-- VALUE { MIN.sub.-- VALUE = ARRAY[I]; MIN.sub.-- INDEX = I; - } }. ______________________________________
After processing each and every one of the N data values in the array, ARRAY, the above pseudo code stores the determined minimum in a parameter MIN.sub.-- VALUE, and stores the location of the minimum in the parameter MIN.sub.-- INDEX.
Previous implementations of such extrema determination procedures are compute intensive. For example, if the pseudo code listed above were implemented with the DSP16000 dual-MAC processor, the compare-select feature of the ALU would implement the comparison step "ARRAY[I]&lt;MIN.sub.-- VALUE" listed above. In such an embodiment, each pass through the FOR loop listed above is implemented in one processing cycle.
It is contemplated that the computational complexity in determining extrema may be reduced by implementing compare-select features in the adder of the DAU, in addition to implementation in the ALU, and that these two units operate in parallel to reduce the number of processing cycles.
A data processor determines an overall extremum value of an input set of array data, with the input set of array data partitionable into a first set of array data and a second set of array data. The data processor includes a pair of compare-select circuits, one implemented in an adder and the other in an arithmetic-logic unit (ALU), the two operate in parallel for concurrent processing of the first and second sets, and for determining respective extremum values for the first and second sets. One compare-select circuit of the pair of compare-select circuits determines the overall extremum value of the input set of array data from the first and second extremum values. The one compare-select circuit also determines the location of the overall extremum value in the input set of array data.